package day11;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入: root = [5,3,6,2,4,null,7], k = 9
 * 输出: true
 * 示例 2：
 *
 *
 * 输入: root = [5,3,6,2,4,null,7], k = 28
 * 输出: false
 *
 *
 */
public class Solution10 {
    Set<Integer> hs= new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        if(root.val-k==0){
            return true;
        }
        hs.add(root.val);
        return dfs(root.right,k)||dfs(root.left,k);
    }
    public boolean dfs(TreeNode node,int i){
        if (node==null){
            return false;
        }
        if(hs.contains(i-node.val)){
            return true;
        }
        hs.add(node.val);
        return dfs(node.right,i)||dfs(node.left,i);
    }
}
